package classic;

/**
 * 丑数：因子只包含2或者3或者5的整数，习惯上1是第一个丑数，
 * 求第n个丑数是多少，例如1是第一个，2是第二个，3是第三个，4是第四个，5是第五个，
 * 6是第六个，8是第七个，9是第八个。。。
 * 直观的解法：从1开始，依次判断一个数是不是丑数，循环直到找到第n个为止，而判断丑数
 * 的方法是循环判断一个数对2求余是否为0，如果是则除以2，直到不能被2整除为止，
 * 对于3和5也是同样的做法，如果最后结果为1说明是丑数，如果最后结果不为1说明不是
 * 但是这种解法的效率很低，每个不是丑数的数都得判断一次，而判断是不是丑数的效率是很低的，
 * 特别是当数值越来越大时。
 * 可以通过空间换时间的办法来提高效率，把每次求出的丑数保存起来，根据规律可以更快地求出结果，
 * 有以下规律：如果已经找到了前n-1个丑数，那么第n个丑数必然是(2乘以其中某个丑数a0)，
 * (3乘以其中某个丑数b0)，(5乘以其中某个丑数c0)三者中间最小的一个，
 * 那么，问题的关键是分别找到a0、b0、c0
 *
 * @author zj
 */
public class UglyNumber {
    public static void main(String[] args) {
        //printUgly2(1500);
        printUgly(1500);
    }

    //高效的解法
    public static void printUgly(int n) {
        if (n <= 0) {
            return;
        } else {
            int[] uglys = new int[n]; //分配一个数组，用来按顺序保存每个丑数
            uglys[0] = 1; //第一个丑数是1
            int nextIndex = 1; //下一个要求出的丑数位置

            //towIndex保存已求出的丑数中这样一个丑数b0的位置，它之前的所有丑数乘以2的结果都小于已有的最大丑数
            //而它之后的所有丑数乘以2的结果都大于已有的最大丑数；threeIndex，fiveIndex分别针对因子3和5的，作用类似
            int towIndex = 0;
            int threeIndex = 0;
            int fiveIndex = 0;
            while (nextIndex < n) {
                //得到下一个丑数
                int nextUgly = min(uglys[towIndex] * 2, uglys[threeIndex] * 3,
                        uglys[fiveIndex] * 5);
                uglys[nextIndex] = nextUgly;
                System.out.println("第 " + (nextIndex + 1) + " 个丑数是：" + nextUgly);

                //然后分别更新三个索引的位置
                while (uglys[towIndex] * 2 <= nextUgly) {
                    towIndex++;
                }
                while (uglys[threeIndex] * 3 <= nextUgly) {
                    threeIndex++;
                }
                while (uglys[fiveIndex] * 5 <= nextUgly) {
                    fiveIndex++;
                }
                nextIndex++;
            }
        }
    }

    public static int min(int a, int b, int c) {
        int min = a < b ? a : b;
        return c < min ? c : min;
    }

    //直观但低效的解法
    public static void printUgly2(int n) {
        if (n <= 0) {
            return;
        } else {
            int uglyNum = 0;
            int number = 1;
            while (uglyNum < n) {
                if (isUgly(number)) {
                    uglyNum++;
                    System.out.println("第 " + uglyNum + " 个丑数是：" + number);
                }
                number++;
            }

        }

    }

    public static boolean isUgly(int number) {
        while (number % 2 == 0) {
            number = number / 2;
        }
        while (number % 3 == 0) {
            number = number / 3;
        }
        while (number % 5 == 0) {
            number = number / 5;
        }
        return (number == 1) ? true : false;
    }
}
